我们知道,bfs是逐层遍历搜索树的算法,所有状态按照如对的先后顺序具有层次单调性,那么当一个状态入队的时候,就得到了从起始状态到达该状态的最少步数。对一些特殊的题目来说,可以用一些适当的转换使得搜索状态具有单调性,从而使用bfs算法解决问题。
leetcode 178周赛的T4(题目编号P1368)
这个题很像一个求最短路径的问题,但是我们可以发现这个题并不满足“走过的路径最短就一定满足修改的次数最短”这个问题,所以这个题不能直接套用bfs走路径的方法来求。
我们可以转换,把求最短距离换成是求最少修改次数,从而这个问题的状态转移就只有两种情况:修改当前方向,代价为1或是不修改当前方向,不需要代价,也就是说把状态转移的代价只有0和1两种,如果我们直接把点插入队列中显然不能满足状态按照进入的方向具有层次单调性的条件,也就不能满足说我求出来的距离一定是最短的。因此我们可以使用双端队列deque,让代价为0的节点插到队头,代价为1的节点插到队尾,这样就解决了单调性的问题,于是我们就可以直接开始用bfs的框架开始搜索,把最短距离换成是最小修改次数来做就可以解决问题了。
这个题题解的代码写得很好,我的代码比较丑就不发了,有需要参考可以去看题解。
SP22393 KATHTHI - KATHTHI
这道题也是很裸的一道题了,由于行走方向只有上下左右四种,因此完全可以参考上面的做法,直接bfs框架+是否相同作为权值来搜索,具体代码请看:https://www.luogu.com.cn/record/31406847